package leetcode_day._2022._202203._1120;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/3/17 19:52
 * 词典中最长的单词
 * 算法：模拟、字典树
 */
public class _17_720 {
    public static void main(String[] args) {
        System.out.println("apple".compareTo("apply"));
    }

    public String longestWord(String[] words) {
        Set<String> set = new HashSet<>(Arrays.asList(words));
        String ans = "";
        for (String s : words) {
            int m = s.length(),  n = ans.length();
            // 剪枝
            if (m < n) continue;
            if (m == n && s.compareTo(ans) > 0) continue;
            StringBuilder tmp = new StringBuilder("");
            int i = 0;
            for (; i < s.length(); i++) {
                tmp.append(s.charAt(i));
                if (!set.contains(tmp.toString())) break;
            }
            if (i == m) ans = s;
        }
        return ans;
    }

    class TrieNode {
        boolean isEnd = false;
        TrieNode[] children = new TrieNode[26];
    }
    void insert(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            if (cur.children[c - 'a'] == null) cur.children[c - 'a'] = new TrieNode();
            cur = cur.children[c - 'a'];
        }
        cur.isEnd = true;
    }
    boolean query(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.children[c - 'a'];
            if (cur == null || !cur.isEnd) return false;
        }
        return cur.isEnd;
    }
    TrieNode root;
    public String longestWord_node(String[] words) {
        root = new TrieNode();
        for (String s : words) insert(s);
        String ans = "";
        for (String s : words) {
            int m = s.length(), n = ans.length();
            if (m < n) continue;
            if (m == n && s.compareTo(ans) > 0) continue;
            if (query(s)) ans = s;
        }
        return ans;
    }

}
